'''
    归并算法： 事先把列表分成两部分，然后继续把这两部分分裂，排序，最后归并到一起的算法，时间复杂度 n log n
'''
import random
def mergeSort(alist):
    if len(alist) > 1:
        middle = len(alist) // 2
        lefthalf = alist[:middle]
        righthalf = alist[middle:]
        print(lefthalf,righthalf,alist)
        mergeSort(lefthalf)
        mergeSort(righthalf)
        i=j=k=0
        while i<len(lefthalf) and j < len(righthalf):
            if lefthalf[i] < righthalf[j]:
                alist[k] = lefthalf[i]
                i += 1
            else:
                alist[k] = righthalf[j]
                j += 1
            k += 1
        while i<len(lefthalf):
            alist[k] = lefthalf[i]
            i += 1
            k += 1
        while j<len(righthalf):
            alist[k] = righthalf[j]
            j += 1
            k += 1

def mergeSort2(lst):
    if len(lst) <= 1:
        return lst
    middle = len(lst) // 2
    left = mergeSort2(lst[:middle])
    right = mergeSort2(lst[middle:])
    l = []
    while left and right:
        if left[0] > right[0]:
            l.append(right.pop(0))
        else:
            l.append(left.pop(0))
    l.extend(right if right else left)
    return l

# l = list(range(6))
l = [5, 2, 1, 3, 4, 0]

# print(l)
print(mergeSort2(l))
# print(l)